﻿/*
 *  PassBag is multi-platform software that securely manage/store passwords
 *  Copyright (C) <2009>  <Hugo Rodrigues PEREIRA>
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *	
 *  You can find a copy of the GPLv3 at project <root directory>/gpl.txt
 *
 */ 
 

namespace PassBag.Utils {
    /// <summary>
    /// Help to calculate the Levenshtein distance
    /// </summary>
    public class StringSimilarity {
        /// <summary>
        /// Levenshtein distance
        /// </summary>
        /// <remarks>
        /// Levenshtein distance is obtained by finding the cheapest 
        /// way to transform one string into another. 
        /// </remarks> 
        /// <see cref="http://www.let.rug.nl/~kleiweg/lev/levenshtein.html">Levenshtein distance theory</see>
        /// <param name="fromString">string one</param>
        /// <param name="toString">string two</param>
        /// <returns>0 if no differences and bigger is the result, larger is the difference</returns>
        public static int DistanceBetween (string fromString, string toString) {
            // get strings length
            int fromStringLength = fromString.Length; 
            int toStringLength = toString.Length; 

            // declare matrix
            int[,] distanceMatrix = new int[fromStringLength + 1, toStringLength + 1];
            // cost            
            int cost; 
            
            // if a string is empty, the distance is the other string length
            if (fromStringLength == 0) return toStringLength;
            if (toStringLength == 0)   return fromStringLength;

            // fill the matrix
            for (int i = 0; i <= fromStringLength; distanceMatrix[i, 0] = i++);
            for (int j = 0; j <= toStringLength; distanceMatrix[0, j] = j++);

            for (int i = 1; i <= fromStringLength; i++) {
                for (int j = 1; j <= toStringLength; j++) {
                    cost = (toString.Substring (j - 1, 1) == fromString.Substring (i - 1, 1) ? 0 : 1);

                    distanceMatrix[i, j] = System.Math.Min (System.Math.Min (distanceMatrix[i - 1, j] + 1, distanceMatrix[i, j - 1] + 1),
                              distanceMatrix[i - 1, j - 1] + cost);
                }

            }

            return distanceMatrix[fromStringLength, toStringLength];

        }

    }

}
